--Funcion provista por la catedra para evaluar una solucion Divide and Conquer a partir de la especificacion de los distintos componentes de la misma.
evalDC :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDC isBase base split join x | isBase x = base x
				| otherwise = join (map (evalDC isBase base split join) (split x))

--Toma dos cadenas y determina si la primer secuencia pasada por parametro es subsecuencia de la segunda secuencia pasada por parametro
--(usa la funcion evalDC provista por la catedra)
subsecuencia :: (Eq a) => ([a],[a]) -> Bool
subsecuencia (x,y) = evalDC isBase base split join (x,y)

--solucion para cadenas contempladas como caso base: se compara su igualdad con la funcion "iguales"
base:: (Eq a) => ([a],[a]) -> Bool
base (xs,ys) = iguales xs ys

--Funcion efectua una comparacion de igualdad entre 2 cadenas, considerando como criterio la igualdad caracter a caracter de ambas cadenas.
iguales:: (Eq a) => [a] -> [a] -> Bool
iguales [] _ = True
iguales (x:xs) [] = False
iguales (x:xs) (y:ys) = (x == y) && (iguales xs ys)

--Consideramos caso base del problema a la situacion en la que ambas cadenas tienen igual longitud, o que la subsecuencia tenga una longitud mayor
--a la secuencia "grande".
isBase:: (Eq a) => ([a],[a]) -> Bool
isBase (xs,ys) = xs == [] || ys == [] || length(xs) >= length(ys)

--Efectuamos el split en 2 problemas mas pequeños: la secuencia sacando su primer caracter, y la secuencia sacando su ultimo caracter.
split:: (Eq a) => ([a],[a]) -> [([a],[a])]
split (xs,(y:ys)) =[(xs,ys),(xs,(init(y:ys)))]

--En el join, teniendo listadas todas las posibles subsecuencias que se pueden formar a partir de la secuencia original (cuyas respectivas 
--longitudes igualan a una subsecuencia S que se desea buscar) se procede a evaluar alguna de dichas subsecuencias es igual a S.
join:: [Bool] -> Bool 
join [] = False
join (x:xs) = x || join xs

--Funcion provista por la catedra para una solucion Divide and Conquer usando tecnicas de programacion dinamica
evalDP :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDP isBase base split join x = solution x (evalDPStore isBase base split join x [])

--Funcion evalDPStore que intenta evaluar una solucion Divide and Conquer propuesta, tratando de evitar recalculos innecesarios en la obtencion
--de la solucion. Esto lo hace buscandolo en una lista de respuestas a soluciones parciales a la que nos referimos como "cache".
--Si la respuesta a la solucion parcial esta dentro de la cache, se busca y se devuelve. Si no lo esta, se soluciona de manera convencional y se
--agrega, esperando que pueda llegar a necesitarse para el calculo de otra futura solucion parcial, o la solucion final del problema. 
evalDPStore :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> [(a,b)] -> [(a,b)]
evalDPStore isBase base split join x cache | solved x cache = cache
					   | isBase x = (x,(base x)):cache
					   | otherwise = (a,b):wx 
	where 
		(a,b) = (x,join(resultados particion))
		wx = soluciones (particion) cache
		particion = split x
		resultados [] = []
		resultados (x:xs) = (solution x wx):(resultados xs)	
		soluciones [] ys = ys
		soluciones (z:zs) ys = soluciones zs (evalDPStore isBase base split join z ys)
		
--Funcion que devuelve la respuesta "b" asociada a un "a", dentro de una lista de tuplas te tipo (a,b) donde "a" es un elemento y "b" su 
--respuesta ligada.
solution :: Eq a => a -> [(a,b)] -> b
solution x (y:ys)
	| x == (fst y) = snd y
	| otherwise = solution x ys

--Funcion que busca en una lista (usada como cache) respuestas a soluciones parciales del problema, a fin de evitar recalculos innecesarios.
solved :: Eq a => a -> [(a,b)] -> Bool
solved x [] = False
solved x (y:ys) = (x == fst y) || solved x ys 

--Toma dos cadenas y determina si la primer secuencia pasada por parametro es subsecuencia de la segunda secuencia pasada por parametro)
--(usa la funcion evalDP provista por la catedra)
subsecuenciaMemo :: (Eq a) => ([a],[a]) -> Bool
subsecuenciaMemo (x,y) = evalDP isBase base split join (x,y)

-- Version numero 1 de fibonacci que utiliza la funcion evalDPStore (en este caso el split consta de 3 subproblemas)
-- Las dos versiones de fibonacci comparten la funcion Join
isBaseFibo1:: Int -> Bool
isBaseFibo1 n = n < 3

baseFibo1:: Int -> Int
baseFibo1 0 = 1
baseFibo1 1 = 1
baseFibo1 2 = 2

splitFibo1:: Int -> [Int]
splitFibo1 n = [(n-2),(n-2),(n-3)]

joinFibo:: [Int] -> Int
joinFibo [] = 0
joinFibo (x:xs) = x + joinFibo xs

fibonacci1 n = evalDP isBaseFibo1 baseFibo1 splitFibo1 joinFibo n

-- Version numero 2 de fibonacci que utiliza la funcion evalDPStore (en este caso el split consta de 2 subproblemas)
isBaseFibo2:: Int -> Bool
isBaseFibo2 n = n < 2

baseFibo2:: Int -> Int
baseFibo2 0 = 1
baseFibo2 1 = 1

splitFibo2:: Int -> [Int]
splitFibo2 n = [(n-1),(n-2)]

fibonacci2 n = evalDP isBaseFibo2 baseFibo2 splitFibo2 joinFibo n		
